package argo.hot100.linklist;

public class MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }

        return mergek(lists, 0, lists.length - 1);
    }

    public ListNode mergek(ListNode[] list, int left, int right) {
        if (left == right) {
            return list[left];
        }
        if (left > right) {
            return null;
        }
        int mid = (right - left) / 2 + left;  // ==> (right+left)/2  => (right+left)>>1
        ListNode list1 = mergek(list, left, mid);
        ListNode list2 = mergek(list, mid + 1, right);
        return merge2Lists(list1, list2);
    }

    public ListNode merge2Lists(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val > head2.val) {
                p.next = head2;
                head2 = head2.next;
            } else {
                p.next = head1;
                head1 = head1.next;
            }
            p = p.next;
        }
        p.next = head1 != null ? head1 : head2;

        return dummy.next;
    }


}
